package algorithms.question.class06;

import common.util.MyUtil;

/**
 * 给定一个整数数组arr，有正有负，求出累加和最大的子数组，返回最大的累加和
 *
 * @author guichang
 * @date 2021/8/3
 */

@SuppressWarnings("all")
public class Code6_子数组的最大累加和 {
    // 以i结尾的子数组中累加和最大，相当于0 - (i-1)前缀和最小的，减去这个最小的就是最大值

    public static void main(String[] args) {
        int LENGTH = 20;
        int MIN = -20;
        int MAX = 20;
        int TIMES = 10000;
        MyUtil.print("测试开始");
        for (int i = 0; i < TIMES; i++) {
            int[] arr = MyUtil.createRandomArray(20, -20, 20);
            if (maxSubSum(arr) != force(arr)) {
                MyUtil.print("Oops!");
                break;
            }
        }
        MyUtil.print("测试结束");
    }

    public static int maxSubSum(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int preSum = 0; // 前缀和
        int preMin = 0; // 前缀最小值
        int max = Integer.MIN_VALUE; // 结果
        for (int i = 0; i < arr.length; i++) {
            preSum += arr[i]; // 计算到i的累加和
            max = Math.max(max, preSum - preMin); // 累加和减去上 0-(i-1)的最小值
            preMin = Math.min(preMin, preSum); // 设置 0-i的最小值
        }
        return max;
    }

    public static int force(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                int subSum = 0;
                for (int k = i; k <= j; k++) {
                    subSum += arr[k];
                }
                max = Math.max(max, subSum);
            }
        }
        return max;
    }
}